import java.util.Arrays;
import java.util.LinkedList;

public class MaxSlidingWindow {

    public static void main(String[] args) {
        int[] nums = {1,3,-1,-3,5,3,6,7};
        MaxSlidingWindow maxSlidingWindow = new MaxSlidingWindow();
        System.out.println(Arrays.asList(maxSlidingWindow.maxSlidingWindow(nums, 3)));
    }

    public int[] maxSlidingWindow(int[] nums, int k) {
        LinkedList<Integer> queue = new LinkedList<>();
        int n = nums.length;
        int[] ans = new int[n - k + 1];
        int l = 0;
        int r = 0;
        while (r < k)  {
            while (!queue.isEmpty() && nums[queue.peekLast()] <= nums[r]) {
                queue.pollLast();
            }
            queue.add(r);
            r++;
        }
        ans[0] = nums[queue.peekFirst()];
        int index = 1;
        while (r < nums.length) {
            if (l == queue.peekFirst()) {
                queue.pollFirst();
            }
            l++;
            while (!queue.isEmpty() && nums[queue.peekLast()] <= nums[r]) {
                queue.pollLast();
            }
            queue.add(r);
            r++;
            ans[index++] = nums[queue.peekFirst()];
        }
        return ans;
    }
}
